package year2023.dfs;


/*N皇后
请设计一种算法，解决著名的n皇后问题。
这里的n皇后问题指在一个n*n的棋盘上放置n个皇后， 使得每行每列和每条对角线上都只有一个皇后(即皇后不能在同一行,不能在同一列,也不能在一条斜线上)，求其摆放的方法数。
 */

public class Code04_QueenN {
    static int n;
    static int cnt;

    static int[] rec;

    public static void main(String[] args){
        n = 4;
        rec = new int[4];
        dfs(0);
        System.out.println(cnt);
    }

    //row表示正在处理的行
    private static void dfs(int row) {
        if (row == n){
            cnt++;
            return;
        }
        //依次尝试在某列上放一个皇后
        for (int col = 0; col < n; col++){
            boolean ok = true;
            //检查这个皇后是否和之前已经放置的皇后有冲突
            for (int i = 0; i < row; i++) {
                if (rec[i] == col || i + rec[i] == row + col || rec[i] - i == col - row){
                    ok = false;
                    break;
                }
            }

            //剪枝
            //这一行这一列可以放
            if (ok){
                rec[row] = col;//标记
                dfs(row + 1); //继续找下一行
                //rec[row] = 0; //恢复原状，但这种解法这里是否恢复状态都行
            }

        }
    }


}
